package org.example.myleet.p1047;

import java.util.Arrays;
import java.util.Stack;

public class Solution {
    /**
     * 21 ms
     * 利用栈记录字符串当前序列，栈顶为候选消除的字符
     */
//    public String removeDuplicates(String S) {
//        Stack<Character> stack = new Stack<>();
//        int n = S.length();
//        for (int i=n-1; i>=0; --i) {
//            char c = S.charAt(i);
//            if (stack.isEmpty()) {
//                stack.push(c);
//            } else {
//                if (c == stack.peek()) {
//                    stack.pop();
//                } else {
//                    stack.push(c);
//                }
//            }
//        }
//        if (0 == stack.size()) {
//            return "";
//        }
//        int i = 0;
//        char[] result = new char[stack.size()];
//        while (!stack.isEmpty()) {
//            result[i++] = stack.pop();
//        }
//        return new String(result);
//    }

    /**
     * 5 ms
     * 使用数组和栈顶指针代替栈
     */
//    public String removeDuplicates(String S) {
//        int n = S.length(), p = 0;
//        char[] result = new char[n];
//        for (int i=0; i<n; ++i) {
//            char c = S.charAt(i);
//            if (p == 0) {
//                result[p++] = c;
//            } else {
//                if (c == result[p-1]) {
//                    --p;
//                } else {
//                    result[p++] = c;
//                }
//            }
//        }
//        if (0 == p) {
//            return "";
//        }
//        return new String(Arrays.copyOf(result, p));
//    }

    /**
     * 12 ms
     * 使用StringBuilder模拟栈操作
     */
    public String removeDuplicates(String S) {
        int n = S.length();
        StringBuilder sb = new StringBuilder(n);
        for (int i=0; i<n; ++i) {
            char c = S.charAt(i);
            if (sb.length() == 0) {
                sb.append(c);
            } else {
                if (c == sb.charAt(sb.length()-1)) {
                    sb.deleteCharAt(sb.length()-1);
                } else {
                    sb.append(c);
                }
            }
        }
        return sb.toString();
    }
}
